package quick_sort

import (
	"time"
	"math/rand"
)

//QuickSort 快速排序
//最坏：O(n^2), 最好 O(nlogn)
//快速排序是不稳定的排序
func QuickSort(nums []int) []int {
	ln := len(nums)
	if ln < 2 {
		return nums
	}
	idx := 0// rand.Intn(ln)
	pivot := nums[idx]
	i := 1
	j := ln-1
	for i != j {

		for nums[j] >= pivot && j > i {
			j--
		}
		for nums[i] < pivot && i < j {
			i++
		}
		
		if i != j {
			nums[i], nums[j] = nums[j], nums[i]
		}
	}
	if nums[idx] > nums[i] {
		nums[idx],nums[i] = nums[i], nums[idx]
	}
	
	QuickSort(nums[:i])
	QuickSort(nums[i:])

	return nums;
}

func init() {
	rand.Seed(time.Now().UnixNano())
}